# LeetCode 39、组合总和

# 一、题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

提示:

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都 互不相同
  • 1 <= target <= 500

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<Integer> path = new ArrayList<>();

        backtrack( candidates , target , path , 0 );

        return res;
    }

    // 1、画出递归树,找到状态变量(回溯函数的参数)
    // start 表示递归时正在访问的数组元素下标
    // nums 表示当前集合中的元素
    // target 表示想在当前区间拼凑出的目标值
    // path 表示选择的路径
    private void backtrack(int[] nums,int target,List<Integer> path,int start) {
    
        // 2、寻找结束条件,由于回溯算法是借助递归实现,所以也就是去寻找递归终止条件
        if (target < 0) {
            // 一些逻辑操作(可有可无,视情况而定)
            // 比如,在 N 皇后问题中,在这一步把数据加入到了结果里面
            return;
        }

        if(target == 0 ){
            
            // 找到一个组合了
            res.add(new ArrayList(path));

            return;
        }
            
        // 3、确定选择列表,即需要把什么数据存储到结果里面
        // for 循环就是一个选择的过程
        // i 等于 start 表示,后续可以选的元素一开始只能从 start 开始
        // 比如 nums = [2,3,6,7]
        // i = 1,指向了元素 3 ,表示当前后续选择的过程中,只能从 3 开始选,可以重复选 3 ,但无法选 2 了
        // i = 2,指向了元素 6 ,表示当前后续选择的过程中,只能从 6 开始选,可以重复选 6 ,但无法选 2、3 了
        for (int i = start ; i < nums.length ; i++ ) {
            
            // 当前路径上可以把 nums[i] 加上
            path.add(nums[i]);
        
            // 一些逻辑操作(可有可无,视情况而定)
            // 4、判断是否需要剪枝,去判断此时存储的数据是否之前已经被存储过
            // 需要剪枝
            // 此时,目标值 target,已经从 target 变成了 target - nums[i]
            // 接下来需要去【某个区间中】拼凑 target - nums[i]
            // 由于 同一个 数字可以 无限制重复被选取
            // 当前正在使用 nums[i],那么为了拼凑 target - nums[i],依旧可以继续从使用 nums[i] 开始
            // 而 i 前面的元素,比如 num[i-1]、 num[i-2]无法继续使用,实现了剪枝操作
            int nowposition = i ; 

            // 5、做出选择,递归调用该函数,进入下一层继续搜索
            // 递归
            backtrack(nums, target - nums[i] , path , nowposition );
        
            // 一些逻辑操作(可有可无,视情况而定)

            // 6、撤销选择,回到上一层的状态
            path.remove(path.size()-1);
        }
    }
}

# Python

class Solution:
    def __init__(self):
        self.res = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        self.backtrack(candidates, target, path, 0)
        return self.res

    # 1、画出递归树,找到状态变量(回溯函数的参数)
    # start 表示递归时正在访问的数组元素下标
    # nums 表示当前集合中的元素
    # target 表示想在当前区间拼凑出的目标值
    # path 表示选择的路径
    def backtrack(self, nums: List[int], target: int, path: List[int], start: int) -> None:
        # 2、寻找结束条件,由于回溯算法是借助递归实现,所以也就是去寻找递归终止条件
        if target < 0:
            # 一些逻辑操作(可有可无,视情况而定)
            # 比如,在 N 皇后问题中,在这一步把数据加入到了结果里面
            return

        if target == 0:
            # 找到一个组合了
            self.res.append(list(path))
            return

        # 3、确定选择列表,即需要把什么数据存储到结果里面
        # for 循环就是一个选择的过程
        # i 等于 start 表示,后续可以选的元素一开始只能从 start 开始
        # 比如 nums = [2,3,6,7]
        # i = 1,指向了元素 3 ,表示当前后续选择的过程中,只能从 3 开始选,可以重复选 3 ,但无法选 2 了
        # i = 2,指向了元素 6 ,表示当前后续选择的过程中,只能从 6 开始选,可以重复选 6 ,但无法选 2、3 了
        for i in range(start, len(nums)):
            # 当前路径上可以把 nums[i] 加上
            path.append(nums[i])
            # 一些逻辑操作(可有可无,视情况而定)
            # 4、判断是否需要剪枝,去判断此时存储的数据是否之前已经被存储过
            # 需要剪枝
            # 此时,目标值 target,已经从 target 变成了 target - nums[i]
            # 接下来需要去【某个区间中】拼凑 target - nums[i]
            # 由于 同一个 数字可以 无限制重复被选取
            # 当前正在使用 nums[i],那么为了拼凑 target - nums[i],依旧可以继续从使用 nums[i] 开始
            # 而 i 前面的元素,比如 num[i-1]、 num[i-2]无法继续使用,实现了剪枝操作
            now_position = i

            # 5、做出选择,递归调用该函数,进入下一层继续搜索
            # 递归
            self.backtrack(nums, target - nums[i], path, now_position)

            # 一些逻辑操作(可有可无,视情况而定)

            # 6、撤销选择,回到上一层的状态
            path.pop()